#pragma once

#include <iostream>
using namespace std;

template <class T>
struct AVLTreeNode
{
    /*将可变参数定义为value_type类型， 用于萃取*/
public:
    typedef T value_type;
    typedef AVLTreeNode<T> avl_node;

    AVLTreeNode(const T &data = T())
        /*这是一个构造函数， 如果没有缺省 值就是普通构造， 并且不会再生成
        默认构造。 但是加上了缺省值， 这就是一个默认构造*/
        : _pLeft(nullptr),
          _pRight(nullptr),
          _pParent(nullptr),
          _data(data),
          _bf(0) /*平衡因子最开始为0*/
    {
    }

    avl_node *_pLeft;
    avl_node *_pRight;
    avl_node *_pParent;
    value_type _data; // 保存的值
    int _bf;          // 平衡因子
};

template <class T>
class AVLTree
{

public:
    typedef AVLTreeNode<T> avl_node;

    AVLTree()
        : _pRoot(nullptr)
    {
    }

    bool InsertAVLTree(const T &data)
    {
        if (_pRoot == nullptr)
        {
            _pRoot = new avl_node(data);
            return true;
        }
        avl_node *parent = nullptr;
        avl_node *cur = _pRoot;
        while (cur)
        {
            if (cur->_data < data)
            {
                parent = cur;
                cur = cur->_pRight;
            }
            else if (cur->_data > data)
            {
                parent = cur;
                cur = cur->_pLeft;
            }
            else
                return false;
        }

        cur = new avl_node(data);
        if (parent->_data > data)
        {
            parent->_pLeft = cur;
        }
        else
        {
            parent->_pRight = cur;
        }
        cur->_pParent = parent; /*当前节点的父节点是parent， 连接起来, 三叉链*/

        /*更新平衡因子*/
        while (parent)
        {
            if (cur == parent->_pLeft)
                parent->_bf--;
            else
                parent->_bf++;

            /*更新*/
            if (parent->_bf == 0)
                break;                                      /*如果平衡因子是0， 那么此时树完美平衡， 退出即可*/
            else if (parent->_bf == 1 || parent->_bf == -1) /*如果平衡因子是1或者-1， 那么树是亚健康， 继续向上检查更新*/
            {
                cur = parent;
                parent = parent->_pParent;
            }
            else if (parent->_bf == 2 || parent->_bf == -2)
            {
                /*旋转操作*/
                /*旋转*/
                if (parent->_bf == -2 && cur->_bf == -1)
                {
                    RotateR(parent);
                }
                else if (parent->_bf == 2 && cur->_bf == 1)
                {
                    RotateL(parent);
                }
                else if (parent->_bf == -2 && cur->_bf == 1)
                {
                    RotateLR(parent);
                }
                else if (parent->_bf == 2 && cur->_bf == -1)
                {
                    RotateRL(parent);
                }
                else
                {
                    cout << "判断旋转失败,平衡因子不符合规则" << endl;
                }

                break;
            }
            else /*更新平衡因子逻辑错误*/
            {
                cout << "更新平衡因子逻辑错误" << endl;
            }
        }

        return true;
    }

    bool IsAVLTree()
    {
        return _IsAVLTree(_pRoot);
    }

    void InOrder()
    {
        _InOrder(_pRoot);
    }

private:
    /*根据AVL树的概念验证_pRoot是否是有效的AVL树*/
    bool _IsAVLTree(avl_node *pRoot)
    {
        return _IsBalence(pRoot);
    }

    int Height(avl_node *pRoot)
    {
        if (pRoot == nullptr)
            return 0;
        int tall_left = Height(pRoot->_pLeft);
        int tall_right = Height(pRoot->_pRight);
        return max(tall_left, tall_right) + 1;
    }

    bool _IsBalence(avl_node *pRoot)
    {
        if (pRoot == nullptr)
            return true;
        int tall_left = Height(pRoot->_pLeft);
        int tall_right = Height(pRoot->_pRight);

        return _IsBalence(pRoot->_pLeft) &&
               _IsBalence(pRoot->_pRight) &&
               (abs(tall_left - tall_right) < 2);
    }

    void _InOrder(avl_node *pRoot)
    {
        if (pRoot == nullptr)
            return;
        /*中序遍历*/
        _InOrder(pRoot->_pLeft);
        cout << pRoot->_data << " " << pRoot->_bf << endl;
        _InOrder(pRoot->_pRight);
    }
    size_t _Height(avl_node *pRoot);
    /*右单旋转*/
    void RotateR(avl_node *pParent)
    {
        avl_node *subL = pParent->_pLeft;
        avl_node *subLR = subL->_pRight;
        avl_node *gparent = pParent->_pParent;

        /*从上到下三次更改， 从下到上三次更改*/
        if (pParent == _pRoot) /*修改子树的父亲节点*/
        {
            _pRoot = subL;
        }
        else
        {
            if (pParent == gparent->_pLeft)
            {
                gparent->_pLeft = subL;
            }
            else
                gparent->_pRight = subL;
        }

        pParent->_pLeft = subLR; /*修改子树的父节点*/
        subL->_pRight = pParent; /*修改子树的子节点*/

        /*从下到上修改三次更改*/

        if (subLR != nullptr) /*修改莫尾节点*/
        {
            subLR->_pParent = pParent;
        }
        pParent->_pParent = subL; /*修改子树的父节点*/
        subL->_pParent = gparent; /*修改子树的子节点*/

        subL->_bf = 0;
        pParent->_bf = 0;
    }
    /*左单旋*/
    void RotateL(avl_node *pParent)
    {
        avl_node *subR = pParent->_pRight;
        avl_node *subRL = subR->_pLeft;
        avl_node *gparent = pParent->_pParent;

        if (gparent == nullptr)
        {
            _pRoot = subR;
        }
        else
        {
            if (gparent->_pLeft == pParent)
                gparent->_pLeft = subR;
            else
                gparent->_pRight = subR;
        }
        pParent->_pRight = subRL;
        subR->_pLeft = pParent;

        if (subRL != nullptr)
            subRL->_pParent = pParent;
        pParent->_pParent = subR;
        subR->_pParent = gparent;

        subR->_bf = 0;
        pParent->_bf = 0;
    }
    /*右左双旋*/
    void RotateRL(avl_node *pParent)
    {
        avl_node *subR = pParent->_pRight;
        avl_node *subRL = subR->_pLeft;
        int bf = subRL->_bf; /*记录subRL的平衡因子， 用于后续进行更新平衡因子*/

        RotateR(subR);
        RotateL(pParent);

        subRL->_bf = 0;
        if (bf == 0)
        {
            subR->_bf = 0;
            pParent->_bf = 0;
        }
        else if (bf == -1)
        {
            pParent->_bf = 0;
            subR->_bf = 1;
        }
        else if (bf == 1)
        {
            pParent->_bf = -1;
            subR->_bf = 0;
        }
        else
        {
            cout << "右左双旋更新平衡因子出现错误" << endl;
        }
    }
    /*左右双旋*/
    void RotateLR(avl_node *pParent)
    {
        avl_node *subL = pParent->_pLeft;
        avl_node *subLR = subL->_pRight;
        int bf = subLR->_bf;

        RotateL(subL);
        RotateR(pParent);

        subLR->_bf = 0;
        if (bf == 0)
        {
            subL->_bf = pParent->_bf = 0;
        }
        else if (bf == -1)
        {
            subL->_bf = 0;
            pParent->_bf = 1;
        }
        else if (bf == 1)
        {
            subL->_bf = -1;
            pParent->_bf = 0;
        }
        else
        {
            cout << "左右双旋更新平衡因子出现错误" << endl;
        }
    }

public:
    static void Test()
    {
        AVLTree<int> avl;

        avl.InsertAVLTree(1);
        avl.InsertAVLTree(5);
        avl.InsertAVLTree(67);
        avl.InsertAVLTree(57);
        avl.InsertAVLTree(47);
        avl.InsertAVLTree(37);
        avl.InsertAVLTree(27);
        avl.InsertAVLTree(17);

        avl.InsertAVLTree(3);
        avl.InsertAVLTree(9);

        avl.InOrder();

        if (avl.IsAVLTree())
            cout << "是AVL树" << endl;
        else
            cout << "不是AVL树" << endl;
    }

private:
    avl_node *_pRoot;
};